import random


def binary_search(seq, target, max_cell=True):
    """
    二分查找，返回相近或者相等数据
    :param seq: 升序容器
    :param target: 目标数据能和seq中的值比较大小
    :param max_cell: 是否向上取整
    :return:
    """
    def _sim(_st, _end, _targ):
        return _st < _targ < _end

    assert bool(seq) and isinstance(seq, (list, tuple, str)), "输入需要是有序可迭代对象，且不能为空"
    if target <= seq[0]:
        return 0
    elif target >= seq[-1]:
        return len(seq) - 1
    start, end = 0, len(seq)
    while start <= end:
        mid = (start + end) // 2
        if seq[mid] == target:
            return mid
        elif seq[mid] < target:
            start = mid + 1
        elif seq[mid] > target:
            end = mid - 1

        if max_cell and _sim(seq[mid], seq[mid + 1], target) and seq[mid + 1] >= target:
            return mid + 1
        elif max_cell and _sim(seq[mid - 1], seq[mid + 1], target) and seq[mid] >= target:
            return mid
        elif (not max_cell) and _sim(seq[mid - 1], seq[mid], target) and seq[mid - 1] <= target:
            return mid - 1
        elif (not max_cell) and _sim(seq[mid - 2], seq[mid - 1], target) and seq[mid - 2] <= target:
            return mid - 2


def gen_seq(num):
    res = []
    for n in range(num):
        if random.choice([True, False]):
            res.append(n)
    return res


if __name__ == '__main__':
    # seq_list = gen_seq(100)
    seq_list = [0, 1, 6, 9, 10, 12, 13, 15, 16, 17, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 35, 39, 42, 44, 47, 49, 50, 51,\
     52, 53, 56, 57, 61, 62, 65, 67, 68, 69, 72, 73, 78, 79, 80, 81, 84, 85, 86, 90, 91, 92, 98, 99]
    print(seq_list)
    index = binary_search(seq_list,100, max_cell=True)
    print("index:{i}; value:{v}".format(i=index, v=seq_list[index]))
